package nowcoder.duoduo3;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

import java.util.Scanner;

public class Main {

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        map = new HashMap<>();
        int[] res = new int[num];
        for(int i = 0; i < num; i++){
            res[i] = inSet(sc.nextInt(), sc.nextInt(), sc.nextInt(), sc.nextInt(), 0) ? 1 : 0;
        }
        for (int i : res){
            System.out.println(i);
        }
    }

    static Map<Integer, Boolean> map = new HashMap<>();

    private static boolean inSet(int A, int B, int C, int Q, int n){
        if(map.containsKey(Q)) return map.get(Q);
        if(Q==A || Q==B || Q==C) return true;
        if(Q<A || Q<B || Q<C) return false;
        boolean r = (inSet(A, B, C, Q - B, n+1) || ((Q / C) * C == Q)) ? inSet(A, B, C, Q / C, n+1) : false;
        map.put(Q, r);
        return r;
    }

}
